#ifndef DBSCAN_H
#define DBSCAN_H

#include <vector>

// Metric Tree includes
#include <arboretum/stMetricTree.h>
#include <arboretum/stPlainDiskPageManager.h>
#include <arboretum/stDiskPageManager.h>
#include <arboretum/stMemoryPageManager.h>
#include <arboretum/stMetricTree.h>
#include <arboretum/stMetricAccessMethod.h>
#include <arboretum/stFMMTree.h>
#include <arboretum/stUserLayerUtil.h>

template <class T>
class ObjectPtr
{
public:
  ObjectPtr(T *pObs)
  {
    mpObject = pObs;
    Serialized = NULL;
  }

  ~ObjectPtr()
  {
    if(Serialized != NULL)
      delete [] Serialized;
  }

  ObjectPtr* Clone()
  {
    return new ObjectPtr(mpObject);
  }

  bool IsEqual(ObjectPtr *obj)
  {
    return(mpObject == obj->mpObject);
  }

  stSize GetSerializedSize()
  {
    return(sizeof(T*));
  }

  const stByte * Serialize()
  {
    if(Serialized == NULL)
    {
      Serialized = new stByte[GetSerializedSize()];
      memcpy(Serialized, &mpObject, sizeof(T*));
    }
    return Serialized;
  }

  void Unserialize(const stByte *data, stSize datasize)
  {
    memcpy(&mpObject, data, sizeof(T*));

    if(Serialized != NULL)
    {
      delete [] Serialized;
      Serialized = NULL;
    }
  }

  T* const GetObject()
  {
    return mpObject;
  }

private:
  T *mpObject;
  stByte * Serialized;   //Serialized version. If NULL, the serialized version is not created.

  // Copy operations are private to prevent copying (except through clone)
  ObjectPtr(const ObjectPtr&); // no implementation 
  ObjectPtr& operator=(const ObjectPtr&); // no implementation 
};

template <class T>
class ObjectPtrDistanceEvaluator : public stMetricEvaluatorStatistics{
public:
  //Returns the similarity distance between 2 mappoints.
  stDistance GetDistance(ObjectPtr<T> *obj1, ObjectPtr<T> *obj2)
  {
    return sqrt(GetDistance2(obj1, obj2));
  }

  //Returns the similarity distance between 2 mappoints raised by the power of 2.
  stDistance GetDistance2(ObjectPtr<T> *obj1, ObjectPtr<T> *obj2)
  {
    UpdateDistanceCount(); // Update Statistics
    return SquaredDistance(obj1->GetObject(), obj2->GetObject());
  }
};

template <class T>
class DBSCAN
{
public:
  DBSCAN(double eps, unsigned int minObs) :  mdEps(eps), mnMinObs(minObs) { };

  void Cluster(std::vector<T*> &vObjects, std::vector<std::vector<T*> > &vClusters) 
  {
    mpObjectTree = new ObjectTree(ObjectTree::rtKEEPSMALL);

    for(unsigned int k = 0; k < vObjects.size(); ++k)
    {
      vObjects[k]->SetUnAssigned();
      mpObjectTree->Add(new ObjectPtr<T>(vObjects[k]));
    }

	  for(unsigned int k = 0; k < vObjects.size(); ++k)
	  {
		  if(vObjects[k]->IsUnAssigned()) // Currently unassigned
        ExpandCluster(vObjects[k], vClusters);
	  }

    delete mpObjectTree;
  }

private:
  void ExpandCluster(T* obs, std::vector<std::vector<T*> > &vClusters)
  {
    // Get the neighbours
    ObjectPtr<T> queryObject(obs);
    stResult<ObjectPtr<T> > *prSeeds = mpObjectTree->RangeQuery(&queryObject, mdEps);

    // not enough support -> mark as noise
    if(prSeeds->GetNumOfEntries() < mnMinObs)
      obs->SetNoise();
    else 
    {
      std::vector<T*> vNewCluster;

      while(prSeeds->GetNumOfEntries() > 0)
      {
        ObjectPtr<T> *cobs = (*prSeeds)[0].GetObject();
        cobs->GetObject()->SetAssigned();
        vNewCluster.push_back(cobs->GetObject());
    
        if(!queryObject.IsEqual(cobs)) // ignore inital point
        {
          stResult<ObjectPtr<T> > *prResult = mpObjectTree->RangeQuery(cobs, mdEps);
          const unsigned int nNumResult = prResult->GetNumOfEntries();

          if(nNumResult >= mnMinObs)
          {
            for(unsigned int j = 0; j < nNumResult; ++j)
            {
              ObjectPtr<T> *robs = (*prResult)[j].GetObject();

              if(robs->GetObject()->IsUnAssigned())
              {
                robs->GetObject()->SetAssigned();
                vNewCluster.push_back(robs->GetObject());
                prSeeds->AddPair(robs->Clone(), 0);
              }
              else if(robs->GetObject()->IsNoise())
              {
                robs->GetObject()->SetAssigned();
                vNewCluster.push_back(robs->GetObject());
              }
            }
          }
          delete prResult;
        }
        prSeeds->RemoveFirst();
      }

      vClusters.push_back(vNewCluster);
    }
    delete prSeeds;
  }

  typedef stFMMTree<ObjectPtr<T>, ObjectPtrDistanceEvaluator<T> > ObjectTree;
  ObjectTree *mpObjectTree;

	const double mdEps;   // Two observations are neighbors if the distance between them does not exceed eps radius.
	const unsigned int mnMinObs;
};

#endif
